package algorithms.leecode;

import java.util.Stack;

public class Au85 {
    public static void main(String[] args) {
        System.err.println(new Au85().maximalRectangle(new char[][]{{'1','0','1','0','0'}
                ,{'1','0','1','1','1'}
                ,{'1','1','1','1','1'},{'1','0','0','1','0'}}));
    }
    public int maximalRectangle(char[][] matrix) {
        int[][] sumX = new int[matrix.length + 2][matrix[0].length];

        for (int j = 0; j < matrix.length; j++) {
            int tmp = 0;
            for (int i = matrix[j].length - 1; i >= 0; i--) {
                if (matrix[j][i] != '0') {
                    tmp++;
                } else {
                    tmp = 0;
                }
                sumX[j + 1][i] = tmp;
            }
        }
        int result = 0;
        for (int i = 0; i < sumX[0].length; i++) {
            Stack<Integer> stk = new Stack<>();
            for (int j = 0; j < sumX.length; j++) {
                while (!stk.isEmpty() && sumX[stk.peek()][i] > sumX[j][i]) {
                    int h = sumX[stk.pop()][i];
                    int l = j - stk.peek() - 1;
                    result = Math.max(result,h * l);
                }
                stk.push(j);
            }

        }
        return result;
    }
}
